class Solution
{
public:
    int retisland = 0;

    void islandSerach(vector<vector<char>>& grid, int x, int y)
    {
        if (x >= grid.size() || y >= grid[0].size()) return;
        if (grid[x][y] == '0') return;

        grid[x][y] = '0';

        islandSerach(grid, x + 1, y);
        islandSerach(grid, x - 1, y);
        islandSerach(grid, x, y - 1);
        islandSerach(grid, x, y + 1);
    }

    int numIslands(vector<vector<char>>& grid)
    {
        int n = grid.size();
        int m = grid[0].size();

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == '1')
                {
                    islandSerach(grid, i, j);
                    retisland += 1;
                }

        return retisland;
    }
};